package cn.edu.jxau.test;

import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {

        int[] arr = { 31, 55, 76, 24, 67, 89, 23, 90, 67, 54, 97, 39, 26, 99, 43, 65, 35 };
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序：就像人们整理扑克牌一样，将一张牌插入到有序的牌组中的适当位置。
     * 
     * 1.特别适合规模不大基本有序的数组
     * 2.最好情况下，时间复杂度是O(n)
     * @param arr
     */
    private static void sort(int[] arr) {

        for(int i=1;i<arr.length;i++) {
            int j=i;
            int temp = arr[j];
            while(j>0 && temp<arr[j-1]) {
                arr[j] = arr[j-1];
                j--;
            }
            arr[j] = temp;
        }
    }
}
